/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						      color_cube.cpp

	$Header: /resource_editor/color_cube.cpp $

	$NoKeywords: $

 ************************************************************************/

// kill the 255+ character identifier warning.  Templates tend to exceed that easily.
#include "precompiled.h"
#pragma warning( disable: 4786 )

#include "color_cube.h"

#include <algorithm>
#include <assert.h>

//------------------------------------------------------------
// color cube.cpp
//------------------------------------------------------------
t_color_cube::t_color_cube()
{
	int i;

	for (i = 0; i < 3; i++)
	{
		m_max_color[i] = 0;
		m_min_color[i] = 0;
	}
}


//------------------------------------------------------------
// find the best location to divide this cube into two volumes
//------------------------------------------------------------
int t_color_cube::find_best_cut( int axis, t_color_sum& best_sum,
								  __int64& best_delta ) const
{
	t_color_sum left_sum;
	t_color_sum right_sum( *this );
	__int64     delta;
	int         color;
	int         best_color = 256;

	t_color_count_list::const_iterator index;

	best_delta = 0;
	index = m_pixels[axis].begin();

	while (index != m_pixels[axis].end())
	{
		color = (*index)->color[axis] + 1;
		while (index != m_pixels[axis].end() && (*index)->color[axis] < color)
		{
			left_sum += **index;
			right_sum -= **index;
			index++;
		}
		if (right_sum.get_count() == 0)
			break;

		delta = left_sum.get_delta() + right_sum.get_delta();
		if (delta < best_delta )
		{
			best_delta = delta;
			best_sum = right_sum;
			best_color = color;
		}
	}
	return best_color;
}

//------------------------------------------------------------
// verify sums are what they should be (debug routine)
//------------------------------------------------------------
void t_color_cube::verify()
{
	t_color_count_list& source = m_pixels[0];
	int sums[3];
	__int64 square_sum = 0;
	int     count = 0;
	int     i;
	t_color_count_list::iterator index;

	memset( sums, 0, sizeof(sums));
	for ( index = source.begin(); index != source.end(); index++)
	{
		for (i = 0; i < 3; i++)
			sums[i] += (*index)->product[i];
		square_sum += (*index)->square_sum;
		count += (*index)->count;
	}
	for (i = 0; i < 3; i++)
		assert( sums[i] == m_sum[i] );
	assert( m_square_sum == square_sum );
	assert( m_count == count );
	if (source.front()->count == count )
	{
		set_variance();
		assert( m_variance == 0);
	}
}

//------------------------------------------------------------
// cut the cube into two smaller color volumes
//------------------------------------------------------------
void t_color_cube::cut( int axis, t_color_cube& right_cube, int color_value )
{
	int i;
	t_color_count_list::iterator index;
	t_color_count_list::iterator last;

	for (i = 0; i < 3; i++)
	{
		t_color_count_list& source = m_pixels[i];
		t_color_count_list& dest   = right_cube.m_pixels[i];

		index = source.begin();
		while (index != source.end())
		{
			last = index;
			index++;
			if ((*last)->color[axis] >= color_value)
			{
				dest.push_back( *last );
				source.erase( last );
			}
		}
		right_cube.m_min_color[i] = m_min_color[i];
		right_cube.m_max_color[i] = m_max_color[i];
		m_sum[i] -= right_cube.m_sum[i];
	}
	m_count -= right_cube.m_count;
	m_square_sum -= right_cube.m_square_sum;
	m_max_color[axis] = color_value;
	right_cube.m_min_color[axis] = color_value;
	set_variance();
	right_cube.set_variance();
}

//------------------------------------------------------------
// cut the cube into the two volumes which minimize the variance.
//------------------------------------------------------------
t_axis t_color_cube::cut( t_color_cube& right_cube )
{
	int          axis;
	int          best_axis = 0;
	t_color_cube new_cubes[3];
	int          color_value[3];
	__int64      delta[3];

	for (axis = 0; axis < 3; axis++)
	{
		color_value[axis] = find_best_cut( axis, new_cubes[axis], delta[axis] );
		if (delta[best_axis] > delta[axis])
			best_axis = axis;
	}
	right_cube = new_cubes[best_axis];
	cut( best_axis, right_cube, color_value[best_axis] );
	return t_axis(best_axis);
}

//------------------------------------------------------------
// sorting order, by axis
//------------------------------------------------------------
namespace {

	class t_color_order
	{
	public:
		t_color_order( int axis ) : m_axis(axis) {}

		bool operator()( t_color_count* left, t_color_count* right )
		{
			return left->color[m_axis] < right->color[m_axis];
		}
	protected:
		int m_axis;
	};

}; // end unnamed namespace

//------------------------------------------------------------
// initialize a color cube from a vector of color counts
//------------------------------------------------------------
void t_color_cube::init( std::vector<t_color_count_ptr>& colors )
{
	int axis;
	std::vector<t_color_count_ptr>::const_iterator source;

	for (axis = 0; axis < 3; axis++)
	{
		std::sort( colors.begin(), colors.end(), t_color_order(axis) );
		for (source = colors.begin(); source != colors.end(); source++)
			m_pixels[axis].push_back( *source );
		m_min_color[axis] = 0;
		m_max_color[axis] = 256;
		m_sum[axis] = 0;
	}

	t_color_count_list::iterator index;
	int     color;
	int     count;
	int     product;
	__int64 square;
	int     i;

	m_count = 0;
	m_square_sum = 0;
	for (index = m_pixels[0].begin(); index != m_pixels[0].end(); index++)
	{
		(*index)->square_sum = 0;
		m_count += (*index)->count;
		for (i = 0; i < 3; i++)
		{
			color = (*index)->color[i];
			count = (*index)->count;
			product = color * count;
			(*index)->product[i] = product;
			square = color * color;
			square *= count;
			(*index)->square_sum += square;
			m_sum[i] += product;
			m_square_sum += square;
		}
	}
	set_variance();
}

//------------------------------------------------------------
// set the palette indexes for the color information
//------------------------------------------------------------
void t_color_cube::set_indexes( t_uint16 label )
{
	t_color_count_list::iterator index;

	for (index = m_pixels[0].begin(); index != m_pixels[0].end(); index++)
		(*index)->index = label;
}
